package com.objcat.playground.leetcode;

/**
 * description: Solution30 <br>
 * date: 2022/3/23 9:53 下午 <br>
 * author: objcat <br>
 * version: 1.0 <br>
 */
public class Solution30 {

    public int firstBadVersion2(int n) {
        // 判断边界
        if (n <= 1) {
            return isBadVersion(n) ? n : 0;
        }
        int s = n;
        while (true) {
            System.out.println(s);
            if (isBadVersion(s) && s > 0) {
                // 如果是坏的版本就对折
                s /= 2;
            } else {
                // 直到找到不是坏的版本后, 就可以确定版版本的区间 就是从 s ~ n
                for (int i = s; i <= n; i++) {
                    if (isBadVersion(i)) {
                        System.out.println("输出: " + i);
                        return i;
                    }
                }
            }
        }
    }

    public int firstBadVersion(int n) {
        int start = 1, end = n;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (!isBadVersion(mid))
                start = mid + 1;
            else
                end = mid;
        }
        return start;
    }

    boolean isBadVersion(int version) {
        if (version >= 1702766719) {
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) {
        Long start = System.currentTimeMillis() / 1000;
        Solution30 solution30 = new Solution30();
        System.out.println(solution30.firstBadVersion(2126753390));
        Long end = System.currentTimeMillis() / 1000;
        System.out.println("用时: " + (end - start));
    }
}
